
# 区间问题先排序，起点升序，起点相同重点降序。
def removeCoveredIntervals(intervals) -> int:
    # 排序，注意顺序，弱条件在前
    intervals = sorted(intervals, key=lambda x: x[1], reverse=True)
    intervals = sorted(intervals, key=lambda x: x[0])
    left, right = 0, 0
    res = 0
    for item in intervals:
        # 被覆盖情况
        if item[0] <= right and item[1] <= right:
            res += 1
        # 相交情况，扩展右端点
        elif item[0] <= right and item[1] > right:
            right = item[1]
        # 完全不想交，重设起点终点：
        elif item[0] > right:
            left, right = item[0], item[1]
    return len(intervals) - res


# 合并重合区间， 对右端点进行判断。
def merge(intervals):
    intervals = sorted(intervals, key=lambda x: x[0])
    res = []
    res.append(intervals[0])
    for item in intervals[1:]:
        last = res[-1]
        if item[0] <= last[1]:
            last[1] = max(last[1], item[1])
        else:
            res.append(item)
    return res

def intervalIntersection(firstList, secondList):
    i, j = 0, 0
    res = []
    while i < len(firstList) and j < len(secondList):
        a1, a2 = firstList[i][0], firstList[i][1]
        b1, b2 = secondList[j][0], secondList[j][1]
        # 有交集的情况：not(a2 < b1 or a1 > b2)
        if b2 >= a1 and a2 >= b1:
            c1 = max(a1, b1)
            c2 = min(a2, b2)
            res.append([c1, c2])
        if b2 < a2:
            j += 1
        else:
            i += 1
    return res


if __name__ == '__main__':
    print(removeCoveredIntervals([[1,4],[3,6],[2,8]]))
    print(merge([[1,3],[2,6],[8,10],[15,18]]))
    print([[0,2],[5,10],[13,23],[24,25]], [[1,5],[8,12],[15,24],[25,26]])
